Title of the article 
CIRCUIT FAILURE ESTIMATE IN THE ROSSER – TURKETT BASIS

Authors 
Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of subdepartment of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia), alehina@pnzgu.ru
Barsukova Oksana Yur'evna, Senior lecturer, subdepartment of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia), kuzya_7@mail.ru

Index UDK 
519.718

Abstract 
Background. In modern mathematics and engineering the theory of synthesis of circuits consisting of unreliable functional elements takes an important place. It should be noted that until now one have used to consider the problems of building reliable circuits, realizing the Boolean functions only. The authors suggest a mathematical model for constructing asymptotically optimal reliable circuit, realizing ternary logics functions. The researchers studied the problem of realization of ternary logic function circuits of unreliable functional elements in the Rosser – Turkett basis. It is assumed that all the basic elements get faulty independently of each other, and any basic element at any input set (with probability 1–2ε) gives the correct value, and, with ε probability, can give any of the two incorrect values. The aim of this work is to obtain lower and upper bounds for reliability of circuits and to construct asymptotically optimal reliable circuits.
Results. As a result of the study the authors managed to prove the previously obtained upper failure estimates, significantly weakening restrictions (previously the probability depended on n – number of variables, functions, and in this work it was replaced by a constant). The authors proved asymptotic accuracy of the upper bounds, i. e. in the Rosser – Turkett basis they found the K class of ternary logic functions, which means that the lower bound for the unreliability of a circuit is asymptotically equal to the upper bound of unreliability for the implementation of any function of this class by any circuit. The K class was explicitly described, as well there was found an estimate for the number of functions, which are included in this class.
Conclusion. It is established that any ternary logic functions can be realized by a circuit that operates with unreliability, asymptotically (at ε → 0), not greater than 6ε. It is proved that the function of K class (containing almost all ternary logic functions) can not be realized by circuits with unreliability, asymptotically (at ε → 0) less than 6ε. Thus almost all ternary logic functions can be realized by asymptotically optimal reliable circuits that operate with unreliability, that is asymptotically equal to 6ε at ε → 0.

Key words 
ternary logics functions, functional elements circuit, unreliability of circuit.


Download PDF 
References 
1. Vasin A. V. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2010, no. 1 (13), pp. 64–79.
2. Grabovskaya S. M. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2011, no. 3 (19), pp. 52–60.
3. Alekhina M. A., Barsukova O. Yu. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2012, no. 1 (21), pp. 57–65.
4. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku [Introduction into discrete mathematics]. Moscow: Nauka, 1986, 384 p.
5. Alekhina M. A. Diskretnaya matematika [Discrete mathematics]. 1993, vol. 5, no. 2, p. 59.
6. Alekhina M. A. Fundamenta Informaticae. 2010, no. 104 (3), pp. 219–222.
